λ¬Έμ
Programmers - μ§κ²λ€λ¦¬ 건λκΈ°
π Logic
public int crossBridge(int[] stones, int k) {
int friends = 0;
int min = Integer.MAX_VALUE;
int max = 0;
// minκ³Ό max μ¬μ΄μ 건λ μ μλ μ΅λ μΈμ μκ° μμ
for (int stone : stones) {
if (stone < min) min = stone;
if (stone > max) max = stone;
}
while (min <= max) {
int mid = (min + max)/2;
// 건λ μ μλ€λ©΄, minμ 1 μ¦κ°μν€κ³ λ°λ³΅
if (canCrossOver(stones, k, mid)) {
min = mid + 1;
friends = mid;
} else {
max = mid - 1;
}
}
return friends;
}
stonesμμ μ΅μκ°, μ΅λκ°μ μ°Ύμ μ΄λΆνμ-
canCrossOver()λ‘midλͺ μ΄ κ±΄λ μ μλμ§ νμΈ- 건λ μ μλ€λ©΄
minμ update - 건λ μ μλ€λ©΄
maxλ₯Ό update
- 건λ μ μλ€λ©΄
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class StoneBridge {
public StoneBridge() {
}
public int crossBridge(int[] stones, int k) {
int friends = 0;
int min = Integer.MAX_VALUE;
int max = 0;
// minκ³Ό max μ¬μ΄μ 건λ μ μλ μ΅λ μΈμ μκ° μμ
for (int stone : stones) {
if (stone < min) min = stone;
if (stone > max) max = stone;
}
while (min <= max) {
int mid = (min + max)/2;
// 건λ μ μλ€λ©΄, minμ 1 μ¦κ°μν€κ³ λ°λ³΅
if (canCrossOver(stones, k, mid)) {
min = mid + 1;
friends = mid;
} else {
max = mid - 1;
}
}
return friends;
}
private boolean canCrossOver(int[] stones, int k, int n) {
int cantOver = 0;
for (int stone : stones) {
// 건λ μ μλ λ
if (stone < n) {
cantOver++;
} else cantOver = 0;
// 건λ μ μλ λλ€λ¦¬κ° kκ° μ°μμ΄λΌλ©΄ 건λ μ μμ!
if (cantOver == k) return false;
}
return true;
}
}
class Solution {
public int solution(int[] stones, int k) {
StoneBridge sb = new StoneBridge();
return sb.crossBridge(stones, k);
}
}
βοΈ Review
- 0μ΄
Kκ° μ°μμ΄λΌλ©΄, λ μ΄μ 건λ μ μλ€λ ν° μ‘°κ±΄μ μ½κ² μ μ μμμΌλ, ν¨μ¨μ± ν μ€νΈκ° μλ κ²μΌλ‘ 보μμ λ, μ΄λ€ μκ³ λ¦¬μ¦μ μ¬μ©ν΄μΌ νλμ§ κ°μ΄ μ€μ§ μμλ€. - κ²μνμμ μ΄λΆ νμμ μ¬μ©νλ€λ κ²μ 보μκ³ , μ½λλ₯Ό λκ° μ°Έκ³ νμλ€. λ³΄κ³ λλ μ μ΄λΆ νμμ μ¬μ©ν΄μΌ νλμ§λ₯Ό μ΄ν΄ν μ μμλ€.